#include "junix.h"
using namespace std;

template<
typename T,
typename Cmp
>
void merge(T a[],int sa,T b[],int sb,T c[]) {
	int ia=0,ib=0,ic=0;
	Cmp cmp;

	while (ia<sa && ib<sb) {
		if (cmp(a[ia],b[ib])) {
			c[ic++] = a[ia++];
		} else {
			c[ic++] = b[ib++];
		}
	}

	for ( ;ia<sa;++ia) 
		c[ic++]=a[ia];
	for (;ib<sb;++ib)
		c[ic++]=b[ib];
}

template <
typename T,
typename Cmp
>
void mergesort(T v[], int size) {
	if (size<=1) return;
	int mid = size/2;
	mergesort<T,Cmp>(v,mid);
	mergesort<T,Cmp>(v+mid,size-mid);

	std::vector<T> tmp(size);
	merge<T,Cmp>(v,mid,v+mid,size-mid,&tmp[0]);
	std::copy(tmp.begin(),tmp.end(),v);
}


int main(int argc, char **argv)
{
	const int sz = 10000000;
	vector<int> V(sz);
	using boost::bind;
	generate(V.begin(), V.end(),
			bind(std::modulus<int>(), bind(rand), sz));

	jtime T;
	T.start();
	mergesort<int,std::less<int> >(&V[0],V.size());
	T.end();
    T.print();

	vector<int>::iterator pos;
	pos = std::adjacent_find(V.begin(),V.end(),std::greater<int>());
	assert(pos == V.end());

//	std::copy(V.begin(),V.end(),
//			std::ostream_iterator<int>(cout," "));
//	std::cout<<std::endl;

}
